/*
 * Copyright (c) 2009-2010 HIT Microelectronic Center
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 * Authors: Gou Pengfei
 *          Jin Yinghan
 *
 * Date: Dec. 2009
 *
 */

#include <list>

#include "config/full_system.hh"
#include "cpu/edge/rob.hh"

using namespace std;

template <class Impl>
EdgeROB<Impl>::EdgeROB(CPU *_cpu, unsigned _numEntries, unsigned _squashWidth,
               std::string _smtEdgeROBPolicy, unsigned _smtEdgeROBThreshold,
               ThreadID _numThreads)
    : cpu(_cpu),
      numEntries(_numEntries),
      squashWidth(_squashWidth),
      numInstBlocksInEdgeROB(0),
      numThreads(_numThreads)
{
    for (ThreadID tid = 0; tid  < numThreads; tid++) {
        squashedSeqNum[tid] = 0;
        doneSquashing[tid] = true;
        threadEntries[tid] = 0;
    }

    std::string policy = _smtEdgeROBPolicy;

    //Convert string to lowercase
    std::transform(policy.begin(), policy.end(), policy.begin(),
                   (int(*)(int)) tolower);

    //Figure out rob policy
    if (policy == "dynamic") {
        robPolicy = Dynamic;

        //Set Max Entries to Total EdgeROB Capacity
        for (ThreadID tid = 0; tid < numThreads; tid++) {
            maxEntries[tid] = numEntries;
        }

    } else if (policy == "partitioned") {
        robPolicy = Partitioned;
        DPRINTF(EdgeROB, "EdgeROB sharing policy set to Partitioned\n");

        //@todo:make work if part_amt doesnt divide evenly.
        int part_amt = numEntries / numThreads;

        //Divide EdgeROB up evenly
        for (ThreadID tid = 0; tid < numThreads; tid++) {
            maxEntries[tid] = part_amt;
        }
    DPRINTF(EdgeROB, "%i entries for each thread in ROB\n", part_amt);

    } else if (policy == "threshold") {
        robPolicy = Threshold;
        DPRINTF(EdgeROB, "EdgeROB sharing policy set to Threshold\n");

        int threshold =  _smtEdgeROBThreshold;;

        //Divide up by threshold amount
        for (ThreadID tid = 0; tid < numThreads; tid++) {
            maxEntries[tid] = threshold;
        }
    } else {
        assert(0 && "Invalid EdgeROB Sharing Policy.Options Are:{Dynamic,"
                    "Partitioned, Threshold}");
    }

    // Set the per-thread iterators to the end of the instruction list.
    for (ThreadID tid = 0; tid < numThreads; tid++) {
        squashIt[tid] = instBlockList[tid].end();
    }

    // Initialize the "universal" EdgeROB head & tail point to invalid
    // pointers
    head = instBlockList[0].end();
    tail = instBlockList[0].end();
}

template <class Impl>
std::string
EdgeROB<Impl>::name() const
{
    return cpu->name() + ".rob";
}

template <class Impl>
void
EdgeROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr)
{
    DPRINTF(EdgeROB, "Setting active threads list pointer.\n");
    activeThreads = at_ptr;
}

template <class Impl>
void
EdgeROB<Impl>::switchOut()
{
    for (ThreadID tid = 0; tid < numThreads; tid++) {
        instBlockList[tid].clear();
    }
}

template <class Impl>
void
EdgeROB<Impl>::takeOverFrom()
{
    for (ThreadID tid = 0; tid  < numThreads; tid++) {
        doneSquashing[tid] = true;
        threadEntries[tid] = 0;
        squashIt[tid] = instBlockList[tid].end();
    }
    numInstBlocksInEdgeROB = 0;

    // Initialize the "universal" EdgeROB head & tail point to invalid
    // pointers
    head = instBlockList[0].end();
    tail = instBlockList[0].end();
}

template <class Impl>
void
EdgeROB<Impl>::resetEntries()
{
    if (robPolicy != Dynamic || numThreads > 1) {
        int active_threads = activeThreads->size();

        list<ThreadID>::iterator threads = activeThreads->begin();
        list<ThreadID>::iterator end = activeThreads->end();

        while (threads != end) {
            ThreadID tid = *threads++;

            if (robPolicy == Partitioned) {
                maxEntries[tid] = numEntries / active_threads;
            } else if (robPolicy == Threshold && active_threads == 1) {
                maxEntries[tid] = numEntries;
            }
        }
    }
}

template <class Impl>
int
EdgeROB<Impl>::entryAmount(ThreadID num_threads)
{
    if (robPolicy == Partitioned) {
        return numEntries / num_threads;
    } else {
        return 0;
    }
}

template <class Impl>
int
EdgeROB<Impl>::countInstBlocks()
{
    int total = 0;

    for (ThreadID tid = 0; tid < numThreads; tid++)
        total += countInstBlocks(tid);

    return total;
}

template <class Impl>
int
EdgeROB<Impl>::countInstBlocks(ThreadID tid)
{
    return instBlockList[tid].size();
}

template <class Impl>
void
EdgeROB<Impl>::insertInstBlock(EdgeBlockPtr &inst_block)
{
    //assert(numInstBlocksInEdgeROB == countInsts());
    assert(inst_block);

    DPRINTF(EdgeROB, "Adding inst block PC %#x to the EdgeROB.\n",
                  inst_block->getStartPC());

    assert(numInstBlocksInEdgeROB != numEntries);

    ThreadID tid = inst_block->getTid();

    instBlockList[tid].push_back(inst_block);

    //Set Up head iterator if this is the 1st inst block in the EdgeROB
    if (numInstBlocksInEdgeROB == 0) {
        // Set the inst block as Non-Speculative
        inst_block->setNonSpeculative();

        head = instBlockList[tid].begin();
        assert((*head) == inst_block);
    }

    //Must Decrement for iterator to actually be valid  since __.end()
    //actually points to 1 after the last inst
    tail = instBlockList[tid].end();
    tail--;

    inst_block->setInEdgeROB();

    ++numInstBlocksInEdgeROB;
    ++threadEntries[tid];

    assert((*tail) == inst_block);

    DPRINTF(EdgeROB, "[tid:%i] Now has %d inst blocks.\n", tid, threadEntries[tid]);
}

template <class Impl>
void
EdgeROB<Impl>::retireHead(ThreadID tid)
{
    //assert(numInstBlocksInEdgeROB == countInsts());
    assert(numInstBlocksInEdgeROB > 0);

    // Get the head EdgeROB instruction.
    InstBlockIt head_it = instBlockList[tid].begin();

    EdgeBlockPtr head_inst_block = (*head_it);

    assert(head_inst_block->readyToCommit());

    DPRINTF(EdgeROB, "[tid:%u]: Retiring head instruction block, "
            "PC %#x,[id:%lli]\n", tid, head_inst_block->getStartPC(),
            head_inst_block->getBlockID());

    --numInstBlocksInEdgeROB;
    --threadEntries[tid];

    head_inst_block->clearInEdgeROB();
    head_inst_block->setCommitted();

    instBlockList[tid].erase(head_it);

    //Update "Global" Head of EdgeROB
    updateHead();

    // @todo: A special case is needed if the inst block being
    // retired is the only inst block in the EdgeROB; otherwise the tail
    // iterator will become invalidated.
    cpu->removeFrontBlock(head_inst_block);
}

template <class Impl>
bool
EdgeROB<Impl>::isHeadReady(ThreadID tid)
{
    if (threadEntries[tid] != 0) {
        return (instBlockList[tid].front())->readyToCommit();
    }

    return false;
}

template <class Impl>
bool
EdgeROB<Impl>::canCommit()
{
    //@todo: set ActiveThreads through EdgeROB or CPU
    list<ThreadID>::iterator threads = activeThreads->begin();
    list<ThreadID>::iterator end = activeThreads->end();

    while (threads != end) {
        ThreadID tid = *threads++;

        if (isHeadReady(tid)) {
            return true;
        }
    }

    return false;
}

template <class Impl>
unsigned
EdgeROB<Impl>::numFreeEntries()
{
    //assert(numInstBlocksInEdgeROB == countInsts());

    return numEntries - numInstBlocksInEdgeROB;
}

template <class Impl>
unsigned
EdgeROB<Impl>::numFreeEntries(ThreadID tid)
{
    return maxEntries[tid] - threadEntries[tid];
}

template <class Impl>
int
EdgeROB<Impl>::doSquash(ThreadID tid)
{
    DPRINTF(EdgeROB, "[tid:%u]: Squashing inst blocks until [sn:%i].\n",
            tid, squashedSeqNum[tid]);

    assert(squashIt[tid] != instBlockList[tid].end());

    if ((*squashIt[tid])->getBlockID() < squashedSeqNum[tid]) {
        DPRINTF(EdgeROB, "[tid:%u]: Done squashing inst blocks.\n",
                tid);

        squashIt[tid] = instBlockList[tid].end();

        doneSquashing[tid] = true;
        return 0;
    }

    bool robTailUpdate = false;
    int num_squashed = 0;

    for (int idx = 0;
         idx < squashWidth &&
         squashIt[tid] != instBlockList[tid].end() &&
         (*squashIt[tid])->getBlockID() > squashedSeqNum[tid];
         ++idx)
    {
        DPRINTF(EdgeROB, "[tid:%u]: Squashing inst blocks PC %#x, Bid: %i.\n",
                (*squashIt[tid])->getTid(),
                (*squashIt[tid])->getStartPC(),
                (*squashIt[tid])->getBlockID());

        if (!(*squashIt[tid])->isSquashed()) {
            num_squashed++;
        }

        // Mark the instruction as squashed, and ready to commit so that
        // it can drain out of the pipeline.
        (*squashIt[tid])->setSquashed();

        (*squashIt[tid])->setCanCommit();


        if (squashIt[tid] == instBlockList[tid].begin()) {
            DPRINTF(EdgeROB, "Reached head of instruction list while "
                    "squashing.\n");

            squashIt[tid] = instBlockList[tid].end();

            doneSquashing[tid] = true;

            return num_squashed;
        }

        InstBlockIt tail_thread = instBlockList[tid].end();
        tail_thread--;

        if ((*squashIt[tid]) == (*tail_thread))
            robTailUpdate = true;

        squashIt[tid]--;
    }

    // Check if EdgeROB is done squashing.
    if ((*squashIt[tid])->getBlockID() <= squashedSeqNum[tid]) {
        DPRINTF(EdgeROB, "[tid:%u]: Done squashing inst blocks.\n",
                tid);

        squashIt[tid] = instBlockList[tid].end();

        doneSquashing[tid] = true;
    }

    if (robTailUpdate) {
        updateTail();
    }

    return num_squashed;
}

template <class Impl>
void
EdgeROB<Impl>::updateHead()
{
    //EdgeBlockPtr head_inst_block;
    TheISA::BlockID lowest_num = 0;
    bool first_valid = true;

    // @todo: set ActiveThreads through EdgeROB or CPU
    list<ThreadID>::iterator threads = activeThreads->begin();
    list<ThreadID>::iterator end = activeThreads->end();

    while (threads != end) {
        ThreadID tid = *threads++;

        if (instBlockList[tid].empty())
            continue;

        if (first_valid) {
            head = instBlockList[tid].begin();
            lowest_num = (*head)->getBlockID();
            first_valid = false;
            continue;
        }

        InstBlockIt head_thread = instBlockList[tid].begin();

        EdgeBlockPtr head_inst_block = (*head_thread);

        assert(head_inst_block != 0);

        if (head_inst_block->getBlockID() < lowest_num) {
            head = head_thread;
            lowest_num = head_inst_block->getBlockID();
        }
    }

    if (first_valid) {
        head = instBlockList[0].end();
    } else { // If there's head valid, mark it as non-speculative.
        (*head)->setNonSpeculative();
    }

}

template <class Impl>
void
EdgeROB<Impl>::updateTail()
{
    tail = instBlockList[0].end();
    bool first_valid = true;

    list<ThreadID>::iterator threads = activeThreads->begin();
    list<ThreadID>::iterator end = activeThreads->end();

    while (threads != end) {
        ThreadID tid = *threads++;

        if (instBlockList[tid].empty()) {
            continue;
        }

        // If this is the first valid then assign w/out
        // comparison
        if (first_valid) {
            tail = instBlockList[tid].end();
            tail--;
            first_valid = false;
            continue;
        }

        // Assign new tail if this thread's tail is younger
        // than our current "tail high"
        InstBlockIt tail_thread = instBlockList[tid].end();
        tail_thread--;

        if ((*tail_thread)->getBlockID() > (*tail)->getBlockID()) {
            tail = tail_thread;
        }
    }
}


template <class Impl>
int
EdgeROB<Impl>::squash(TheISA::BlockID squash_num, ThreadID tid)
{
    if (isEmpty()) {
        DPRINTF(EdgeROB, "Does not need to squash due to being empty "
                "[sn:%i]\n",
                squash_num);

        return 0;
    }

    DPRINTF(EdgeROB, "Starting to squash within the EdgeROB.\n");

    robStatus[tid] = EdgeROBSquashing;

    doneSquashing[tid] = false;

    squashedSeqNum[tid] = squash_num;

    if (!instBlockList[tid].empty()) {
        InstBlockIt tail_thread = instBlockList[tid].end();
        tail_thread--;

        squashIt[tid] = tail_thread;

        return doSquash(tid);
    }

    // No inst block has been squashed this cycle.
    return 0;
}

template <class Impl>
typename Impl::EdgeBlockPtr
EdgeROB<Impl>::readHeadInstBlock(ThreadID tid)
{
    if (threadEntries[tid] != 0) {
        InstBlockIt head_thread = instBlockList[tid].begin();

        assert((*head_thread)->isInEdgeROB()==true);

        return *head_thread;
    } else {
        return dummyInstBlock;
    }
}

template<class Impl>
TheISA::BlockID
EdgeROB<Impl>::readHeadInstBlockID(ThreadID tid)
{
    if (threadEntries[tid] != 0) {
        InstBlockIt head_thread = instBlockList[tid].begin();

        assert((*head_thread)->isInEdgeROB()==true);

        return (*head_thread)->getBlockID();
    } else {
        return 0;
    }
}

template <class Impl>
typename Impl::EdgeBlockPtr
EdgeROB<Impl>::readTailInstBlock(ThreadID tid)
{
    InstBlockIt tail_thread = instBlockList[tid].end();
    tail_thread--;

    return *tail_thread;
}

